package com.bee.剑指offer;

import java.util.List;
import java.util.Stack;

/**
 * @version 1.0.0
 * @Author yong.Mr
 * @data 2021-03-10
 */
public class 反转链表 {
    /**
     * 反转链表
     */
    public static ListNode ReverseList(ListNode head) {
        ListNode cur = head;
        ListNode pre = null;
        while (cur != null) {
           ListNode temp = cur.next;

           cur.next = pre;
           // 始终指向前一个节点
           pre = cur;

           cur = temp;
        }
        return pre;
    }

    public static ListNode reverse(ListNode head) {
        if(head == null) {
            return null;
        }
        ListNode cur = head;
        ListNode pre = null;
        while (cur != null) {
            ListNode temp = cur.next;
            cur.next = pre;

            pre = cur;
            cur = temp;
        }
        return pre;
    }

    /**
     * 利用栈的特性进行反转
     */
    public static ListNode ReverseList2(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        while (head!=null) {
            stack.push(head);
            head = head.next;
        }
        if(stack.isEmpty()) {
            return null;
        }
        ListNode node = stack.pop();
        ListNode result = node;
        while (!stack.isEmpty()) {
            ListNode pop = stack.pop();
            node.next = pop;
            node = pop;
        }
        node.next = null;
        return result;
    }

    public static void main(String[] args) {
        ListNode listNode = new ListNode(67);
        listNode.next = new ListNode(0);
        listNode.next.next = new ListNode(24);
        listNode.next.next.next = new ListNode(58);
        ListNode result = ReverseList2(listNode);
        ListNode temp = result;
        while (temp != null){
            System.out.println(temp.val);
            temp = temp.next;
        }
    }

    public static class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

}
